<html>
<head>
 <title>GENOTYPES</title>
</head>

<body>

<center>
<h1>POI IV Stage II Problem 2</h1>
<h1>Genotypes</h1>
</center>

<p>
<b>Genotype</b> is a finite sequence of genes. It can be described by words built of
capital letters A-Z of the English alphabet. Different letters denote different kinds
of genes. A gene can bud and in effect transform into a pair of new genes. Such
transformations are controlled by a finite set of rules. Every <b>rule of budding</b>
can be described by three capital letters  
A<sub>1</sub>A<sub>2</sub>A<sub>3</sub>. Such a description means that gene A<sub>1</sub> can
transform into the pair of genes A<sub>2</sub>A<sub>3</sub>.</p>

<p>We are using S to denote the special kind of genes called 
<b>supergenes</b>. The breeding of a genotype begins from a sequence of supergenes
and it consists in controlled budding of chosen genes according to the given rules.
</p>

<p>
<h2>Task</h2>
Write a program that:
<ul>
<li>reads from the text file GEN.IN a finite set of budding rules and a sequence of
words describing genotypes which we want to breed, 
<li>for every given genotype checks if it can be bred from a certain finite
sequence of supergenes according to the given budding rules and if so
finds the minimal length of such a sequence,
<li>writes the result to the text file GEN.OUT.
</ul>
</p>

<p>
<h2>Input</h2>
In the first line of the text file GEN.IN there is one integer n,
1 &lt;= n &lt;= 10000. In each of the following n lines there is one budding rule.
Such a rule is described by a word consisting of three capital letters A - Z.
</p>

<p>In the next line there is written one integer k,
1 &lt;= k &lt;= 10000. In each of the following k lines there is one genotype.
Such a genotype is described by a non-empty word consisting of at most 100 letters A - Z.
</p>

<p>
<h2>Output</h2>
In the i-th of k lines of the text file GEN.OUT there should be written:
<ul>
<li>one positive integer - the minimal length of a sequence of supergenes
needed to breed the i-th of the given genotypes, or
<li>the word NIE (which means NO in Polish), if such a genotype can not be bred.
</ul>
</p>

<p>
<h2>Example</h2>
For the file GEN.IN:
<pre>6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA</pre>
the correct solution is file GEN.OUT:
<pre>3
1
NIE</pre>
</p>

</body>
</html>
